/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class SubarraySumsDivisiblebyK {
	public int subarraysDivByK(int[] A, int K) {
		int n = A.length;
		int sum = 0;
		HashMap<Integer, ArrayList<Integer>> yuAndI = new HashMap<>();
		for (int i = 0; i < n; i++) {
			sum += A[i];
			int yu = sum % K;
			if (yu < 0) {
				yu += K;
			}
			if (yuAndI.containsKey(yu)) {
				yuAndI.get(yu).add(i);
			} else {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				yuAndI.put(yu, list);
			}
		}
		int res = 0;
		for (Integer yu : yuAndI.keySet()) {
			int size = yuAndI.get(yu).size();
			int cnt = 0;
			if (yu == 0) {
				cnt = size * (size + 1) / 2;
			} else {
				cnt = size * (size - 1) / 2;
			}
			res += cnt;
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { -9, 2, 9 };// { 4, 5, 0, -2, -3, 1 };
		int K = 2;// 5;
		System.out.println(new SubarraySumsDivisiblebyK().subarraysDivByK(A, K));
	}

}
